package learn.sort;

import java.util.Arrays;

/**
 * @author 于昂
 * Date 2021/1/10
 * Time 9:59
 */
public class InsertSort {
    public static void main(String[] args) {
//        int[] array = {101, 34, 109, 1,};
        int[] array = new int[80000];
        for (int i = 0; i < array.length; i++) {
            array[i] = (int) (Math.random() * 800000);
        }
        Long startTime = System.currentTimeMillis();
        insertSort(array);
        Long endTime = System.currentTimeMillis();
        long tempTime = (endTime - startTime);
        System.out.println("花费时间：" +
                (((tempTime / 86400000) > 0) ? ((tempTime / 86400000) + "d") : "") +
                ((((tempTime / 86400000) > 0) || ((tempTime % 86400000 / 3600000) > 0)) ? ((tempTime % 86400000 / 3600000) + "h") : ("")) +
                ((((tempTime / 3600000) > 0) || ((tempTime % 3600000 / 60000) > 0)) ? ((tempTime % 3600000 / 60000) + "m") : ("")) +
                ((((tempTime / 60000) > 0) || ((tempTime % 60000 / 1000) > 0)) ? ((tempTime % 60000 / 1000) + "s") : ("")) +
                ((tempTime % 1000) + "ms"));
    }

    private static void insertSort(int[] array) {
        for (int i = 1; i < array.length; i++) {//除了第一个数其他都有参与对比
            int temp = array[i]; //要插入的值
            int index = i-1; //假设 前一位就是要插入的位置
            while (index >= 0 && temp < array[index]) {//index >= 0防止数组越界  temp < array[index] 插入目标位置大于临时值
                array[index+1] = array[index]; //数组变为 {101, 101, 109, 1,} 将原本待插入值的位置由其前一个元素填充
                index--;//指针前移
            }
            array[index + 1] = temp;
//            System.out.print(Arrays.toString(array));
        }
    }
}
